package com.company;

import java.util.Random;

/**
 * @ClassName:
 * @author:
 * @Description:
 * @Date
 **/
//在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//输入: [3,2,1,5,6,4] 和 k = 2
//输出: 5

//[3,2,1,5,6,4]
//2
public class Leetcode215 {
    public static int findKthLargest(int[] nums, int k) {
        Random rnd = new Random();
        return selectK(nums, 0, nums.length - 1, nums.length - k, rnd);
    }


    //双路快速排序的思想，分区
    public static int partition(int nums[], int l, int r, Random rnd) {
        int p = l + rnd.nextInt(r - l + 1);
        swap(nums, l, p);//此时l为标定点
        // arr[l+1...i-1] <= v; arr[j+1...r] >= v
        // 前指针
        int i = l + 1;
        //后指针
        int j = r;
        while (true) {
            while (i <= j && nums[i] < nums[l]) {
                i++;
            }
            while (j >= i && nums[j] > nums[l]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
            i++;
            j--;
        }
        swap(nums, l, j);
        return j;
    }

    //求第K个大的数字其实是求第arr.length-k的小的数字
    private static int selectK(int[] arr, int l, int r, int k, Random rnd) {
        int p = partition(arr, l, r, rnd);
        if (k == p) {
            return arr[p];
        }
        if (k < p) {
            //继续递归排序
            return selectK(arr, 1, p - 1, k, rnd);
        }
        //继续递归排序 返回的是k比p大的情况
        return selectK(arr, p + 1, r, k, rnd);
    }

    //selectK的非递归写法
    private static int selectK(int[] arr, int k, Random rnd) {
        //arr[l,r]
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int p = partition(arr, l, r, rnd);
            if (k == p) {
                return arr[p];
            } else if (k < p) {
                //如果k比标定点小，则缩小左边区间
                r = p - 1;
            } else {
                l = p + 1;
            }
        }
        throw new RuntimeException("no solution");
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k = 4;
        System.out.println(findKthLargest(nums, k));
    }
}
